首页 > 试题广场 >

数组中出现次数超过一半的数字

[编程题]数组中出现次数超过一半的数字

热度指数：848911 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围： $n \le 50000$ ，数组中元素的值 $0 \le val \le 10000$

要求：空间复杂度： $O(1)$ ，时间复杂度 $O(n)$

输入描述:

保证数组输入非空，且保证有解

示例1

输入

[1,2,3,2,2,2,5,4,2]

输出

示例2

输入

[3,3,3,3,2,2,2]

输出

示例3

输入

[1]

输出

算法知识视频讲解

推荐

peter7788

方法一：采用用户“分形叶”思路（注意到目标数超过数组长度的一半，对数组同时去掉两个不同的数字，到最后剩下的一个数就是该数字。如果剩下两个，那么这两个也是一样的，就是结果），在其基础上把最后剩下的一个数字或者两个回到原来数组中，将数组遍历一遍统计一下数字出现次数进行最终判断。

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int length=array.length;
     if(array==null||length<=0){
     return 0;
     }

     if(length==1){
     return array[1];
     }

     int[] tempArray=new int[length];
     for(int i=0;i<length;i++){
     tempArray[i]=array[i];
     }

     for(int i=0;i<length;i++){
     //后面需要用零来代表抹除数字，所以对0时做特殊处理
     if(tempArray[i]==0){
     continue;
     }

     for(int j=i+1;j<length;j++){
          if(tempArray[i]!=tempArray[j]&&tempArray[j]!=0){
     tempArray[i]=0;//此处用0代表抹去该数字
     tempArray[j]=0;
     break;
     }

     }
     }

     for(int i=0;i<length;i++){
          System.out.println(tempArray[i]);
     }

     //找出未被抹去的数字
     int result=0;
     for(int i=0;i<length;i++){
     if(tempArray[i]!=0){
     result=tempArray[i];
     break;
     }
     }

     int times=0;
     for(int i=0;i<length;i++){
     if(result==array[i]){

     times++;
     }
     }

     if(times*2<length){
     result=0;
     }
     return result;
}
}

方法二：剑指offer解法二（个人觉得与方法一基本就是同一个意思，异曲同工之妙）

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int length=array.length;
     if(array==null||length<=0){
     return 0;
     }

int result=array[0];
     int times=1;
for(int i=1;i<length;i++){
if(times==0){
result=array[i];
times=1;
}else{
if(array[i]==result){
times++;
}else{
times--;
}
}
}

times=0;
for(int i=0;i<length;i++){
if(result==array[i]){
times++;
}
}

if(times*2<length){
result=0;
}
return result;
}
}

编辑于 2015-06-19 17:18:47 回复(111)

Python 3

在努力存钱的查理很甜美

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param numbers int整型一维数组

# @return int整型

# import re

class Solution:

def MoreThanHalfNum_Solution(self, numbers: List[int]) -> int:

# write code here

a = str(numbers)

numbers.sort()

b = 0

c = []

print(numbers)

if len(numbers)<=1:

return numbers[0]

for i in numbers:

if i not in c:

c = []

c.append(i)

elif i in c and len(c)>=len(numbers)/2:

return c[0]

break

c.append(i)

发表于 2023-03-24 02:08:30 回复(0)

Python 3

秋叶红霜CCCCCC

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        count = 0
        candidate = None
        for i in numbers:
            if count == 0: # 票为0，先换候选人
                candidate = i
            count += 1 if i == candidate else -1 # 投给候选人，则票数+1，头给别人，票数-1
        return candidate

发表于 2022-11-06 11:47:49 回复(0)

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        d=dict()
        for num in numbers:
            if not d.get(num):
            #target-numbers[i-1],则放入哈希表中
                d[num]=1
            else:
                d[num]+=1
        d1=sorted(d.items(),key=lambda x:x[1])
        return d1[-1][0]

发表于 2022-08-20 15:08:24 回复(0)

Python 3

牛客96188058号

两行代码搞定，解题思路：有重复数字超过数组长度的一半，那么排序后，数字中间的数字必定是该数字。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        numbers.sort()
        return numbers[len(numbers)//2]

发表于 2022-07-18 18:44:06 回复(0)

Python 3

YiMo_以沫

1. 排序之后最中间的数一定是出现超过一半的数字。时间复杂度O(NlogN)，不稳定。

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        return sorted(numbers)[len(numbers) >> 1]

2. 找众数，题目保证有解，所以众数一定是出现超过一半的数字。

先预设众数preNum和出现的次数count。

遍历数组，若count == 0，说明现在还没有众数，保存在preNum中并将count置为1。

若count > 0，则表示现在有众数，判断当前的数是否等于预设的众数，如等于将count + 1，若不等于则将count - 1.

注意最后count中并不是众数出现的次数。

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        preNum, count = 0, 0
        for i in numbers:
            if count:
                count = count + 1 if preNum == i else count - 1
            else:
                preNum, count = i, 1
        return preNum

发表于 2022-06-21 10:26:06 回复(0)

Python 3

来牛客玩玩

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        if len(numbers) == 1:
            return numbers[0]
        for x in set(numbers):
            if numbers.count(x) > len(numbers)//2:
                return x

发表于 2022-06-20 22:48:56 回复(0)

Python 3

曰无衣bupt

一个一个的检查太麻烦了，而且对于大的数组时间复杂度更高。

直接借助set：

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in set(numbers):
            if numbers.count(i)>len(numbers)/2:
                return i

发表于 2022-06-15 17:44:00 回复(0)

Python 3

牛客647218893号

def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        has = {}
        res = []

        for i in range(len(numbers)):
            if numbers[i] in has:
                has[numbers[i]] += 1
            else:
                has[numbers[i]] = 1
            if has[numbers[i]] > int(len(numbers)/2):
                res = numbers[i]
        return res

发表于 2022-06-13 16:34:19 回复(0)

Python 3

东方佑

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in set(numbers):
            if numbers.count(i)>len(numbers)//2:
                return i

发表于 2022-06-08 18:22:25 回复(0)

Python 3

Vivimore

在保证一定有解的情况下，可以使用这种方法时间复杂度O(n) 空间复杂度O(1)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        temp = -1
        cnt = 0
        for num in numbers:
            if cnt == 0:
                temp = num
                cnt += 1
            else:
                if num == temp:
                    cnt += 1
                else:
                    cnt -= 1
        return temp

哈希法
时间复杂度：O(n) 空间复杂度O(n)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        n = len(numbers)
        mp = {}
        for num in numbers:
            if num not in mp:
                mp[num] = 1
            else:
                mp[num] += 1
            if mp[num] >= n / 2:
                return num

发表于 2022-05-18 21:47:51 回复(0)

Python 3

哦啦啦啊哦哦

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        rating=0
        for num in numbers:
            if rating==0:
                res=num 
            if num == res:
                rating +=1
            else:
                rating -=1
        return res

# 直观的话就是哈希表记录每个字符出现的次数但是时间空间复杂度都是O(n)
# 用摩尔投票就会让空间复杂度变O(1)
# 因为这道题肯定是出现次数最多的为解
# 但是简单说的话就是先设置第一个是m 票数设为1 后面是m的就+1 不是m就-1
# 直到票数变为0 重新设一个m 票数也重新记为1
# 原理不懂但是试一试确实是这样

发表于 2022-05-06 16:31:12 回复(0)

Python 3

牛客394879911号

class Solution:
def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
# write code here
len1=len(numbers)/2
dict1=dict()
for i in numbers:
if i not in dict1:
dict1[i]=1
else:
dict1[i]+=1
for k,v in dict1.items():
if v>=len1:
return k

发表于 2022-04-29 09:57:32 回复(0)

Python 3

danspace

from collections import Counter
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        d = Counter(numbers)
        return d.most_common(1)[0][0]

发表于 2022-04-19 14:58:28 回复(0)

Python 3

想搞机器学习的小白

摩尔投票

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        #投票
        count = 0
        for num in numbers:
            if count==0:half = num
            if num==half:
                count+=1
            else:count-=1
        return half

发表于 2022-04-12 16:07:26 回复(0)

Python 3

路痴喵

请问python使用内置函数遍历后超时，有没有什么解决方法呀？比如下面这样：

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in numbers:
            if numbers.count(i) > len(numbers)//2:
                return i

发表于 2022-03-21 23:03:16 回复(0)

Python 3